package com.ma.DataStruct.trietree;

import java.util.ArrayList;
import java.util.List;

/*
在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)。
例如，词根an，跟随着单词other(其他)，可以形成新的单词another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子
 */
public class Solution648 {
    public static void main(String[] args) {
       /*   输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
            输出："the cat was rat by the bat"
        */
        List<String> dictionary = new ArrayList<String>();
        dictionary.add("cat");
        dictionary.add("bat");
        dictionary.add("rat");
        String sentence = "the cattle was rattled by the battery";
        String s = replaceWords(dictionary, sentence);
        System.out.println(s);

    }

    public static String replaceWords(List<String> dictionary, String sentence) {
        Trie1 trie1 = new Trie1();
        for (String word : dictionary) {
            trie1.insert(word);
        }
        String[] queryWords = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String query : queryWords) {
            String s = trie1.shortestPrefixOf(query);
            sb.append(s+" ");
        }
        return sb.substring(0,sb.length()-1);
    }
}

class Trie1 {

    TrieNode root;

    public Trie1() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i)-'a';
            if (curr.children[c] == null) {
                curr.children[c] = new TrieNode();
            }
            curr = curr.children[c];
        }
        curr.isWord = true;
    }

    public String shortestPrefixOf(String query) {
        TrieNode cur = root;
        for (int i = 0; i < query.length(); i++) {
            if (cur == null) {
                return query;
            }
            if (cur.isWord) {
                return query.substring(0, i);
            }
            int c = query.charAt(i) - 'a';
            cur = cur.children[c];
        }

        return query;
    }


    class TrieNode {
        boolean isWord;
        TrieNode[] children;

        public TrieNode() {
            isWord = false;
            children = new TrieNode[26];
        }
    }

}
